package huawei;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 代码超时
 *
 * @Author Jun jie Yi
 * 2022/3/30 21:27
 */

public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = {-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        //接受返回值
        List<List<Integer>> r = new ArrayList<>();
        if (nums.length < 3) {
            return r;
        }
        List<List<Integer>> ls = new ArrayList<>();
        //拿到两两组合的所有情况
        int flag = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && flag == 0) flag = 1;
            for (int j = i + 1; j < nums.length; j++) {
                //1.存取的第一个数 2.存取的第二个数 3.存储的他们的和
                List<Integer> element = new ArrayList<>();
                element.add(i);
                element.add(j);
                element.add(nums[i] + nums[j]);
                ls.add(element);
            }
        }
        if (flag == 0) {
            List<Integer> l = new ArrayList<>();
            l.add(0);
            l.add(0);
            l.add(0);
            r.add(l);
            return r;
        }
        for (int k = 0; k < ls.size(); k++) {
            List<Integer> e = ls.get(k);
            for (int i = 0; i < nums.length; i++) {
                if (e.get(0) != i && e.get(1) != i && e.get(2) + nums[i] == 0) {
                    List<Integer> ee = new ArrayList<>();
                    ee.add(nums[e.get(0)]);
                    ee.add(nums[e.get(1)]);
                    ee.add(nums[i]);
                    //看是否有重复
                    boolean b = true;
                    for (int j = 0; j < r.size(); j++) {
                        List<Integer> le = r.get(j);
                        //去重复
                        Set<Integer> les = new HashSet<>(le);
                        Set<Integer> ees = new HashSet<>(ee);
                        if (le.containsAll(ee) && les.size() == ees.size()) {
                            b = false;
                            break;
                        }
                    }
                    if (b) {
                        r.add(ee);
                    }
                }
            }
        }
        return r;
    }
}
